#include <iostream>
#include <vector>
#include <string>
using namespace std;

class Solution {
	int min_count(string &s, int l, int r, vector<vector<int>> &dp)
	{
		if (l == r) {
			return 1;
		}

		if (l + 1 == r) {
			if (s[l] == s[r]) {
				return 1;
			} else {
				return 2;
			}
		}

		if (dp[l][r] != -1) {
			return dp[l][r];
		}

		if (s[l] == s[r]) {
			return dp[l][r] = min_count(s, l, r - 1, dp);
		}

		int ans = INT32_MAX;
		for (int p = l; p < r; p++) {
			ans = min(ans, min_count(s, l, p, dp) + min_count(s, p + 1, r, dp));
		}

		return dp[l][r] = ans;
	}

    public:
	int strangePrinter(string s)
	{
		int n = s.size();
		vector<vector<int>> dp(n, vector<int>(n, -1));
		return min_count(s, 0, n - 1, dp);
	}
};

int main()
{
	string s = "aaabbb";
	cout << Solution().strangePrinter(s)<<endl;
	return 0;
}